package org.tony.algorithms;

import java.util.Arrays;

/**
 * 给定一个数组，求其连续的子数组之和最大的子数据
 * @author tony
 *
 */
public class FindMaxSumSubSet
{

	public static int[] find(int[] src)
	{
		int ending = 0 , i = 0;
		int maxsofar , end;
		maxsofar = end = 0;

		for (; i < src.length; i++)
		{
			end = max(end + src[i], 0);
			if (maxsofar < end)
			{
				maxsofar = end;
				ending = i;
			}
		}
		int start = ending;
		while (maxsofar > 0)
		{
			int temp = src[start--];
			maxsofar = maxsofar - temp;
		}
		return Arrays.copyOfRange(src, start + 1, ending + 1);
	}

	static int max(int n1 , int n2)
	{
		return n1 >= n2 ? n1 : n2;
	}

	public static void main(String[] args)
	{
		int a[] = { 3, -3, 5, -10, -7, 8 };
		int b[] = find(a);
		for (int i : b)
		{
			System.out.print(i + " ");
		}
	}

}
